package com.le.medium.class8;

import org.junit.Test;

/**
 * 给定一个全是小写字母的字符串str，删除多余字符，使得每种字符只保留一个，并让 最终结果字符串的字典序最小
 * 【举例】 str = "acbc"，删掉第一个'c'，得到"abc"，是所有结果字符串中字典序最小的。
 * str = "dbcacbca"，删掉第一个'b'、第一个'c'、第二个'c'、第二个'a'，得到"dabc"，
 * 是所有结 果字符串中字典序最小的。
 */
public class Problem06_RemoveDuplicateLettersLessLexi {

    public static String getString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        return process(s);
    }

    private static String process(String s) {
        if (s.length() == 0 || s == null) {
            return "";
        }
        char[] chs = s.toCharArray();
        int[] map = new int[256];
        for (int i = 0; i < chs.length; i++) {
            ++map[chs[i]];
        }
        int minIndex = 0;
        for (int i = 0; i < chs.length; i++) {
            minIndex = chs[i] < chs[minIndex] ? i : minIndex;
            if (--map[chs[i]] == 0) {
                break;
            }
        }
        return String.valueOf(chs[minIndex]) +
                process(s.substring(minIndex + 1).replaceAll(String.valueOf(chs[minIndex]), ""));
    }

    @Test
    public void test() {
        String str = "acbc";
        String str1 = "dbcacbca";
        System.out.println(getString(str));
        System.out.println(getString(str1));
    }
}
